/**
 * 我们从二叉树的根节点 root开始进行深度优先搜索。
 *
 * 在遍历中的每个节点处，我们输出D条短划线（其中D是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
 *
 * 如果节点只有一个子节点，那么保证该子节点为左子节点。
 *
 * 给出遍历输出S，还原树并返回其根节点root。
 *https://leetcode.cn/problems/recover-a-tree-from-preorder-traversal/
 * 思路：利用'-'的数量然后先序递归
 *
 */
class RecoverFromPreorderDiGui {
    int index=0;
    public TreeNode recoverFromPreorder(String traversal) {
        int len=traversal.length();
        return recoverFromPreorder(traversal,0,len,false);
    }
    public TreeNode recoverFromPreorder(String traversal,int count,int len,boolean falg){
        if(index>=len){
            return null;
        }
        int tmp=0;
        while(traversal.charAt(index)=='-'){
            tmp++;
            index++;
        }
        if(tmp<=count&&falg){
            index-=tmp;
            return null;
        }
        falg=true;
        StringBuilder str=new StringBuilder();
        while(index<len&&traversal.charAt(index)!='-'){
            str.append(traversal.charAt(index));
            index++;
        }
        TreeNode root=new TreeNode(Integer.valueOf(str.toString()));
        root.left=recoverFromPreorder(traversal,tmp,len,true);
        root.right=recoverFromPreorder(traversal,tmp,len,true);
        return root;
    }
}